// Copyright 2017 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_WASM_BASELINE_LIFTOFF_REGISTER_H_
#define V8_WASM_BASELINE_LIFTOFF_REGISTER_H_

#include <iosfwd>
#include <memory>

#include "src/base/bits.h"
#include "src/wasm/baseline/liftoff-assembler-defs.h"
#include "src/wasm/wasm-opcodes.h"

namespace v8 {
namespace internal {
    namespace wasm {

        static constexpr bool kNeedI64RegPair = kSystemPointerSize == 4;

        enum RegClass : uint8_t {
            kGpReg,
            kFpReg,
            // {kGpRegPair} equals {kNoReg} if {kNeedI64RegPair} is false.
            kGpRegPair,
            kNoReg = kGpRegPair + kNeedI64RegPair
        };

        enum RegPairHalf : uint8_t { kLowWord = 0,
            kHighWord = 1 };

        static inline constexpr bool needs_reg_pair(ValueType type)
        {
            return kNeedI64RegPair && type == kWasmI64;
        }

        // TODO(clemensh): Use a switch once we require C++14 support.
        static inline constexpr RegClass reg_class_for(ValueType type)
        {
            return needs_reg_pair(type) // i64 on 32 bit
                ? kGpRegPair
                : type == kWasmI32 || type == kWasmI64 // int types
                    ? kGpReg
                    : type == kWasmF32 || type == kWasmF64 // float types
                        ? kFpReg
                        : kNoReg; // other (unsupported) types
        }

        // Maximum code of a gp cache register.
        static constexpr int kMaxGpRegCode = 8 * sizeof(kLiftoffAssemblerGpCacheRegs) - base::bits::CountLeadingZeros(kLiftoffAssemblerGpCacheRegs) - 1;
        // Maximum code of an fp cache register.
        static constexpr int kMaxFpRegCode = 8 * sizeof(kLiftoffAssemblerFpCacheRegs) - base::bits::CountLeadingZeros(kLiftoffAssemblerFpCacheRegs) - 1;
        // LiftoffRegister encodes both gp and fp in a unified index space.
        // [0 .. kMaxGpRegCode] encodes gp registers,
        // [kMaxGpRegCode+1 .. kMaxGpRegCode + kMaxFpRegCode] encodes fp registers.
        // I64 values on 32 bit platforms are stored in two registers, both encoded in
        // the same LiftoffRegister value.
        static constexpr int kAfterMaxLiftoffGpRegCode = kMaxGpRegCode + 1;
        static constexpr int kAfterMaxLiftoffFpRegCode = kAfterMaxLiftoffGpRegCode + kMaxFpRegCode + 1;
        static constexpr int kAfterMaxLiftoffRegCode = kAfterMaxLiftoffFpRegCode;
        static constexpr int kBitsPerLiftoffRegCode = 32 - base::bits::CountLeadingZeros<uint32_t>(kAfterMaxLiftoffRegCode - 1);
        static constexpr int kBitsPerGpRegCode = 32 - base::bits::CountLeadingZeros<uint32_t>(kMaxGpRegCode);
        static constexpr int kBitsPerGpRegPair = 1 + 2 * kBitsPerGpRegCode;

        // int kMaxGpRegCode;
        // int kMaxFpRegCode;
        // int kAfterMaxLiftoffGpRegCode;
        // int kAfterMaxLiftoffFpRegCode;
        // int kAfterMaxLiftoffRegCode;
        // int kBitsPerLiftoffRegCode;
        // int kBitsPerGpRegCode;
        // int kBitsPerGpRegPair;

        class LiftoffRegister {
            static constexpr int needed_bits = Max(kNeedI64RegPair ? kBitsPerGpRegPair : 0, kBitsPerLiftoffRegCode);
            using storage_t = std::conditional<needed_bits <= 8, uint8_t, std::conditional<needed_bits <= 16, uint16_t, uint32_t>::type>::type;

            static_assert(8 * sizeof(storage_t) >= needed_bits, "chosen type is big enough");
            // Check for smallest required data type being chosen.
            // Special case for uint8_t as there are no smaller types.
            static_assert((8 * sizeof(storage_t) < 2 * needed_bits) || (sizeof(storage_t) == sizeof(uint8_t)), "chosen type is small enough");

        public:
            explicit LiftoffRegister(Register reg)
                : LiftoffRegister(reg.code())
            {
                DCHECK_NE(0, kLiftoffAssemblerGpCacheRegs & reg.bit());
                DCHECK_EQ(reg, gp());
            }
            explicit LiftoffRegister(DoubleRegister reg)
                : LiftoffRegister(kAfterMaxLiftoffGpRegCode + reg.code())
            {
                DCHECK_NE(0, kLiftoffAssemblerFpCacheRegs & reg.bit());
                DCHECK_EQ(reg, fp());
            }

            static LiftoffRegister from_liftoff_code(uint32_t code)
            {
                DCHECK_LE(0, code);
                DCHECK_GT(kAfterMaxLiftoffRegCode, code);
                DCHECK_EQ(code, static_cast<storage_t>(code));
                return LiftoffRegister(code);
            }

            static LiftoffRegister from_code(RegClass rc, int code)
            {
                switch (rc) {
                case kGpReg:
                    return LiftoffRegister(Register::from_code(code));
                case kFpReg:
                    return LiftoffRegister(DoubleRegister::from_code(code));
                default:
                    UNREACHABLE();
                }
            }

            static LiftoffRegister ForPair(Register low, Register high)
            {
                DCHECK(kNeedI64RegPair);
                DCHECK_NE(low, high);
                storage_t combined_code = low.code() | high.code() << kBitsPerGpRegCode | 1 << (2 * kBitsPerGpRegCode);
                return LiftoffRegister(combined_code);
            }

            constexpr bool is_pair() const
            {
                return kNeedI64RegPair && (code_ & (1 << (2 * kBitsPerGpRegCode))) != 0;
            }
            constexpr bool is_gp() const { return code_ < kAfterMaxLiftoffGpRegCode; }
            constexpr bool is_fp() const
            {
                return code_ >= kAfterMaxLiftoffGpRegCode && code_ < kAfterMaxLiftoffFpRegCode;
            }

            LiftoffRegister low() const { return LiftoffRegister(low_gp()); }

            LiftoffRegister high() const { return LiftoffRegister(high_gp()); }

            Register low_gp() const
            {
                DCHECK(is_pair());
                static constexpr storage_t kCodeMask = (1 << kBitsPerGpRegCode) - 1;
                return Register::from_code(code_ & kCodeMask);
            }

            Register high_gp() const
            {
                DCHECK(is_pair());
                static constexpr storage_t kCodeMask = (1 << kBitsPerGpRegCode) - 1;
                return Register::from_code((code_ >> kBitsPerGpRegCode) & kCodeMask);
            }

            Register gp() const
            {
                DCHECK(is_gp());
                return Register::from_code(code_);
            }

            DoubleRegister fp() const
            {
                DCHECK(is_fp());
                return DoubleRegister::from_code(code_ - kAfterMaxLiftoffGpRegCode);
            }

            int liftoff_code() const
            {
                DCHECK(is_gp() || is_fp());
                return code_;
            }

            RegClass reg_class() const
            {
                return is_pair() ? kGpRegPair : is_gp() ? kGpReg : kFpReg;
            }

            bool operator==(const LiftoffRegister other) const
            {
                DCHECK_EQ(is_pair(), other.is_pair());
                return code_ == other.code_;
            }
            bool operator!=(const LiftoffRegister other) const
            {
                DCHECK_EQ(is_pair(), other.is_pair());
                return code_ != other.code_;
            }
            bool overlaps(const LiftoffRegister other) const
            {
                if (is_pair())
                    return low().overlaps(other) || high().overlaps(other);
                if (other.is_pair())
                    return *this == other.low() || *this == other.high();
                return *this == other;
            }

        private:
            storage_t code_;

            explicit constexpr LiftoffRegister(storage_t code)
                : code_(code)
            {
            }
        };
        ASSERT_TRIVIALLY_COPYABLE(LiftoffRegister);

        inline std::ostream& operator<<(std::ostream& os, LiftoffRegister reg)
        {
            if (reg.is_pair()) {
                return os << "<" << reg.low_gp() << "+" << reg.high_gp() << ">";
            } else if (reg.is_gp()) {
                return os << reg.gp();
            } else {
                return os << reg.fp();
            }
        }

        class LiftoffRegList {
        public:
            class Iterator;

            static constexpr bool use_u16 = kAfterMaxLiftoffRegCode <= 16;
            static constexpr bool use_u32 = !use_u16 && kAfterMaxLiftoffRegCode <= 32;
            using storage_t = std::conditional<
                use_u16, uint16_t,
                std::conditional<use_u32, uint32_t, uint64_t>::type>::type;

            static constexpr storage_t kGpMask = storage_t { kLiftoffAssemblerGpCacheRegs };
            static constexpr storage_t kFpMask = storage_t { kLiftoffAssemblerFpCacheRegs }
                << kAfterMaxLiftoffGpRegCode;

            constexpr LiftoffRegList() = default;

            Register set(Register reg) { return set(LiftoffRegister(reg)).gp(); }
            DoubleRegister set(DoubleRegister reg)
            {
                return set(LiftoffRegister(reg)).fp();
            }

            LiftoffRegister set(LiftoffRegister reg)
            {
                if (reg.is_pair()) {
                    regs_ |= storage_t { 1 } << reg.low().liftoff_code();
                    regs_ |= storage_t { 1 } << reg.high().liftoff_code();
                } else {
                    regs_ |= storage_t { 1 } << reg.liftoff_code();
                }
                return reg;
            }

            LiftoffRegister clear(LiftoffRegister reg)
            {
                if (reg.is_pair()) {
                    regs_ &= ~(storage_t { 1 } << reg.low().liftoff_code());
                    regs_ &= ~(storage_t { 1 } << reg.high().liftoff_code());
                } else {
                    regs_ &= ~(storage_t { 1 } << reg.liftoff_code());
                }
                return reg;
            }

            bool has(LiftoffRegister reg) const
            {
                if (reg.is_pair()) {
                    DCHECK_EQ(has(reg.low()), has(reg.high()));
                    reg = reg.low();
                }
                return (regs_ & (storage_t { 1 } << reg.liftoff_code())) != 0;
            }
            bool has(Register reg) const { return has(LiftoffRegister(reg)); }
            bool has(DoubleRegister reg) const { return has(LiftoffRegister(reg)); }

            constexpr bool is_empty() const { return regs_ == 0; }

            constexpr unsigned GetNumRegsSet() const
            {
                return base::bits::CountPopulation(regs_);
            }

            constexpr LiftoffRegList operator&(const LiftoffRegList other) const
            {
                return LiftoffRegList(regs_ & other.regs_);
            }

            constexpr LiftoffRegList operator|(const LiftoffRegList other) const
            {
                return LiftoffRegList(regs_ | other.regs_);
            }

            constexpr bool operator==(const LiftoffRegList other) const
            {
                return regs_ == other.regs_;
            }
            constexpr bool operator!=(const LiftoffRegList other) const
            {
                return regs_ != other.regs_;
            }

            LiftoffRegister GetFirstRegSet() const
            {
                DCHECK(!is_empty());
                int first_code = base::bits::CountTrailingZeros(regs_);
                return LiftoffRegister::from_liftoff_code(first_code);
            }

            LiftoffRegister GetLastRegSet() const
            {
                DCHECK(!is_empty());
                int last_code = 8 * sizeof(regs_) - 1 - base::bits::CountLeadingZeros(regs_);
                return LiftoffRegister::from_liftoff_code(last_code);
            }

            LiftoffRegList MaskOut(const LiftoffRegList mask) const
            {
                // Masking out is guaranteed to return a correct reg list, hence no checks
                // needed.
                return FromBits(regs_ & ~mask.regs_);
            }

            RegList GetGpList() { return regs_ & kGpMask; }
            RegList GetFpList() { return (regs_ & kFpMask) >> kAfterMaxLiftoffGpRegCode; }

            inline Iterator begin() const;
            inline Iterator end() const;

            static LiftoffRegList FromBits(storage_t bits)
            {
                DCHECK_EQ(bits, bits & (kGpMask | kFpMask));
                return LiftoffRegList(bits);
            }

            template <storage_t bits>
            static constexpr LiftoffRegList FromBits()
            {
                static_assert(bits == (bits & (kGpMask | kFpMask)), "illegal reg list");
                return LiftoffRegList(bits);
            }

            template <typename... Regs>
            static LiftoffRegList ForRegs(Regs... regs)
            {
                LiftoffRegList list;
                for (LiftoffRegister reg : { LiftoffRegister(regs)... })
                    list.set(reg);
                return list;
            }

        private:
            storage_t regs_ = 0;

            // Unchecked constructor. Only use for valid bits.
            explicit constexpr LiftoffRegList(storage_t bits)
                : regs_(bits)
            {
            }
        };
        ASSERT_TRIVIALLY_COPYABLE(LiftoffRegList);

        static constexpr LiftoffRegList kGpCacheRegList = LiftoffRegList::FromBits<LiftoffRegList::kGpMask>();
        static constexpr LiftoffRegList kFpCacheRegList = LiftoffRegList::FromBits<LiftoffRegList::kFpMask>();

        class LiftoffRegList::Iterator {
        public:
            LiftoffRegister operator*() { return remaining_.GetFirstRegSet(); }
            Iterator& operator++()
            {
                remaining_.clear(remaining_.GetFirstRegSet());
                return *this;
            }
            bool operator==(Iterator other) { return remaining_ == other.remaining_; }
            bool operator!=(Iterator other) { return remaining_ != other.remaining_; }

        private:
            explicit Iterator(LiftoffRegList remaining)
                : remaining_(remaining)
            {
            }
            friend class LiftoffRegList;

            LiftoffRegList remaining_;
        };

        LiftoffRegList::Iterator LiftoffRegList::begin() const
        {
            return Iterator { *this };
        }
        LiftoffRegList::Iterator LiftoffRegList::end() const
        {
            return Iterator { LiftoffRegList {} };
        }

        static constexpr LiftoffRegList GetCacheRegList(RegClass rc)
        {
            return rc == kFpReg ? kFpCacheRegList : kGpCacheRegList;
        }

        inline std::ostream& operator<<(std::ostream& os, LiftoffRegList reglist)
        {
            os << "{";
            for (bool first = true; !reglist.is_empty(); first = false) {
                LiftoffRegister reg = reglist.GetFirstRegSet();
                reglist.clear(reg);
                os << (first ? "" : ", ") << reg;
            }
            return os << "}";
        }

    } // namespace wasm
} // namespace internal
} // namespace v8

#endif // V8_WASM_BASELINE_LIFTOFF_REGISTER_H_
